/**
 * 338. 比特位计数
 * https://leetcode-cn.com/problems/counting-bits/
 */
const { displayBaseArray } = require('../../libs/public');

/**
 * @param {number} n
 * @param {number[]} dp
 * @return {number}
 */
function complete(n, dp) {
  if (!n) return 0;
  if (dp[n] > 0) {
    return dp[n];
  }
  dp[n] = complete(n >> 1, dp) + (n & 1);
  return dp[n];
}

/**
 * @param {number} n
 * @return {number[]}
 */
function countBits(n) {
  const dp = new Array(n + 1).fill(0);
  for (let i = n; i > 0; i -= 1) {
    complete(i, dp);
  }
  return dp;
}

console.log(displayBaseArray(countBits(2)) === '[0,1,1]');
console.log(displayBaseArray(countBits(5)) === '[0,1,1,2,1,2]');
